/*
 * Arbre peut étendre de la même classe que Graphe
 */

package Base;

import java.util.LinkedList;

/**
 * 
 */
class Arbre {

	protected LinkedList<Connexe> foret;
	protected Graphe g;

	public Arbre(Graphe g){
		this.g=g;
		foret=new LinkedList<Connexe>();
		for(Connexe c:g.composantesConnexe)
		{
			foret.add(arbreCouvrant(c.arretes, c.sommets));
		}
	}

	/**
	 * Construit l'arbre couvrant d'un graphe
	 * Construire l'arbre couvrant revient à effectuer une recherche dans un graphe
	 * Cette méthode utilise la recherche ne largeur
	 * @return arbre couvrant
	 */
	public Connexe arbreCouvrant (LinkedList<Arete> arestes,LinkedList<SommetBase> sommets) {

		System.out.println("\t\tCalcul de l'arbre couvrant...");
		
		LinkedList<Arete> aretesArbre=new LinkedList<Arete>();
		LinkedList<SommetBase> enCours=new LinkedList<SommetBase>();
		LinkedList<SommetBase> sommetsMarques=new LinkedList<SommetBase>();
		LinkedList<SommetBase> voisins=new LinkedList<SommetBase>();
		SommetBase tmp=null;

		sommetsMarques.add(sommets.getFirst());
		enCours.add(sommets.getFirst());

		while(!enCours.isEmpty())
		{
			tmp=enCours.removeFirst();
			voisins=g.voisins(tmp);
			for(SommetBase voisin:voisins)
			{
				if(!sommetsMarques.contains(voisin))
				{
					sommetsMarques.add(voisin);
					enCours.addLast(voisin);
					aretesArbre.add(g.getArete(tmp, voisin));
				}
			}
		}

		return new Connexe(aretesArbre, sommets);
	}


	/**
	 * Retourne les arêtes témoins d'un graphe en connaissant son arbre couvrant
	 * @param aretesGraphe
	 * @param aretesArbre
	 * @return liste d'Arêtes témoins
	 */
	public LinkedList<Arete> calculTemoin (LinkedList<Arete> aretesGraphe,LinkedList<Arete> aretesArbre) {
		
		System.out.println("\t\tRecherche des arêtes témoins...");
		
		LinkedList<Arete> temoins=new LinkedList<Arete>(aretesGraphe);

		for(Arete a:aretesArbre)
		{
			temoins.remove(a);
		}

		return temoins;
	}

	/**
	 * Retourne la liste de toutes les arêtes de l'arbre
	 * @return Liste des arêtes de l'arbre
	 */
	public LinkedList<Arete> getAretes(){
		LinkedList<Arete> arete=new LinkedList<Arete>();
		for(Connexe c:foret){
			arete.addAll(c.arretes);
		}
		return arete;
	}

}